\chapter{Uogólnione gry przestrzenne}\label{uogolnioneGryPrzestrzenne}

\newcommand{\graUP}{\gra^{UP}}
\newcommand{\dyn}{\mathfrak{D}}
\newcommand{\nat}{\mathbb{N}}
\newcommand{\real}{\mathbb{R}}
\newcommand{\neigh}[1]{\mathcal{N}(#1)}
% \DeclareMathOperator{\rand}{rand} % TODO tego powinienem uzyc
\newcommand{\rand}{rand}
\newcommand{\nieznany}{\bot}
\newcommand{\upp}{\bar{q}}
\newcommand{\uppy}{\bar{\mathcal{Q}}} % TODO brzydkie
\newcommand{\typ}{\tau}
\newcommand{\typy}{\mathcal{T}}
\newcommand{\pref}{\pi}
\newcommand{\prefy}{\Pi}
\newcommand{\chary}{\Gamma}
\newcommand{\mapaC}{\mu}
\newcommand{\mapyC}{\mathcal{M}}
\newcommand{\mapaSy}{\psi}
\newcommand{\mapySy}{\Psi}
\newcommand{\mapaSt}{\phi}
\newcommand{\mapySt}{\Phi}
\newcommand{\ctx}{\mathfrak{C}}
\newcommand{\udeg}[1]{\overline{deg}(#1)}

Gry przestrzenne, zaprezentowane w poprzednim rozdziale na przykładzie
modelu społeczeństwa polskiego, opisują interakcje między graczami umieszczonymi
w wierzchołkach \emph{grafu}.
Ich rywalizacja jest wyznaczona przez daną \emph{symetryczną grę dwuosobową}
$\gra$ oraz graf, na którym symulacja się odbywa.
Wypłaty z gier są kumulowane i od nich zależą decyzje graczy w następnej turze.
Dynamika sieci jest jednak zupełnie niezależna od dynamiki populacji.

W tym rozdziale przedstawimy teraz uogólnienie tej koncepcji.
Uzależnimy graf od gry i jej przebiegu za pomocą relacji sympatii
(por. \ref{uogolnionyProfilPrzestrzenny}, \ref{relacjaSympatii}, \ref{fwwk}).
Rozszerzymy możliwości kumulowania wypłat (punkt \ref{laczneWyplaty}).
Wreszcie zdefiniujemy używane przez nas dynamiki, które zostaną
sformalizowane za pomocą łańcuchów Markowa w sekcji
\ref{dynamikaJakoLancuchMarkowa}.

Wszystkie zmienne losowe występujące w tym rozdziale są określone na
przestrzeni probabilistycznej $\tuple{\mathcal{P}, \Omega, \mathcal{F}}$, której
nie będziemy szczegółowo charakteryzować.

W rozdziale tym często mamy do czynienia ze zbiorami par ---
wierzchołków wraz z ich sąsiadami. Dla czytelności,
przyjmujemy konwencję, że napis postaci $ V \times \neigh{V} $ 
oznacza zbiór $\bigcup_{v \in V}\ \{v\} \times \neigh{v}$.

\section{Definicje}

Celem tej części jest zdefiniowanie konceptów \emph{uogólnionej gry przestrzennej}
oraz \emph{uogólnionego profilu przestrzennego}.
Przed sformalizowaniem  głównych pojęć wprowadzimy ich małe części
składowe, które uogólniają kolejne aspekty modelu przedstawionego w poprzednim
rozdziale.

\subsection{Mapa strategii}\label{mapaStrategii}

\emph{Mapa strategii} jest to funkcja ze zbioru wierzchołków $V$ w zbiór
strategii $S$ i reprezentuje ona wybór strategii dokonany przez każdego z
graczy.

\begin{df}
Niech $\gra$ będzie grą, a $\graf$ dowolnym grafem.
\emph{Mapą strategii} dla grafu u $\graf$ nazwiemy dowolną funkcję
\[ \mapaSt : V \to S \]
Zbiór wszystkich takich funkcji będziemy oznaczać jako $\mapySt = S^V$.
\end{df}

\subsection{Relacja sympatii}\label{relacjaSympatii}

Istotną zmianą w porównaniu do modelu z rozdziału \emph{\nameref{modelPolski}}
jest sposób wyrażania dynamiki grafu.
W uogólnionych grach przestrzennych zakładamy, że graf jest stały (np. pełny),
natomiast zmiany w nim są realizowane poprzez manipulowanie wagami krawędzi.
Są one wyliczane na podstawie \emph{relacji sympatii} graczy, której definicja
przedstawia się następująco.

\begin{df}
Niech $\graf$ będzie dowolnym grafem.
\emph{Relacją sympatii} nazwiemy dowolną funkcję
\[ \mapaSy : V \times \neigh{V} \to [0,1] \]
Przyjmujemy, że sympatia gracza $v$ względem gracza $w$ 
rośnie wraz ze wzrostem wartości $\mapaSy(v,w)$.
Zbiór wszystkich relacji sympatii będziemy oznaczali
$\mapySy = [0,1]^{V \times \neigh{V}}$.
\end{df}

\noindent
Zauważmy, że relacja sympatii wcale nie musi być symetryczna,
tzn. może się zdarzyć, że $\mapaSy(v,w) \neq \mapaSy(w,v)$.

\subsection{Wagi krawędzi}\label{fwwk}

Relacja sympatii $\mapaSy$ z każdą krawędzią grafu wiąże
dwie wartości z przedziału $[0,1]$, które stanowią odzwierciedlenie zażyłości
między wierzchołkami incydentnymi z tą krawędzią.
Z ich pomocą obliczamy wagę krawędzi --- liczbę, która opisuje
jak mocno połączeni są ze sobą gracze i jak bardzo chcą ze sobą grać.
Informację tę dla wygody przedstawiamy w postaci funkcji
$\fwwk$ przyporządkowującej krawędziom ich wagi.

\begin{df}
Niech $\graf$ będzie grafem.
\emph{Funkcją wyboru wagi krawędzi} nazwiemy dowolną funkcję
\[ \fwwk : V \times \neigh{V} \to [0,1], \]
która jest symetryczna.
\end{df}

\noindent
Rozważamy następujące warianty \emph{funkcji wyboru wagi krawędzi}.

\begin{df}\label{fwwkavg}
\emph{Funkcja wyboru wagi krawędzi} \emph{średnia} jest równa
\[ \fwwk_{avg}^\mapaSy(v, w) = (1/2)(\mapaSy(v,w) + \mapaSy(w,v)) \]
\end{df}

\begin{df}\label{fwwkmax}
\emph{Funkcja wyboru wagi krawędzi} \emph{maksimum} jest równa
\[ \fwwk_{max}^\mapaSy(v, w) = \max\{\mapaSy(v,w), \, \mapaSy(w,v)\} \]
\end{df}

\begin{df}\label{fwwkmin}
\emph{Funkcja wyboru wagi krawędzi} \emph{minimum} jest równa
\[ \fwwk_{min}^\mapaSy(v, w) =  \min\{\mapaSy(v,w), \, \mapaSy(w,v)\} \]
\end{df}

\subsection{Uogólniony stopień wierzchołka}\label{udeg}

Będziemy potrzebowali uogólnionej definicji stopnia wierzchołka,
uwzględniającej relację sympatii $\mapaSy$ oraz funkcję $\fwwk$.

\begin{df}
Uogólnionym stopniem wierzchołka $\udeg{v}$ będziemy nazywali sumę
\[ \udeg{v} = \sum_{w \in \neigh{v}}{\fwwk^\mapaSy(v, w)} \]
\end{df}

\subsection{Wypłata}\label{laczneWyplaty}

Dla ustalonego grafu $\graf$, gry $\gra = \tuple{I, S, u}$ oraz funkcji wyboru
wag krawędzi $\fwwk$ możemy określić sposób obliczania \emph{łącznych wypłat}
uzyskiwanych przez graczy w jednej turze.
\begin{df}
Funkcją \emph{łącznej wypłaty} nazwiemy dowolne odwzorowanie
\[\wyplata : \mapySy \times \mapySt \times V \to \real \]
\end{df}

\noindent
Rozważamy kilka sposobów obliczania łącznej wypłaty:

\begin{df}\label{wyplataStandardowa}
Łączna wypłata \emph{standardowa} wierzchołka $v$ jest równa
\[ U_{st}(\mapaSy, \mapaSt ,v) = \sum_{w \in \neigh{v}} \fwwk^\mapaSy(v,w) \cdot u(\mapaSt(v), \mapaSt(w)) \]
\end{df}

\begin{df}\label{wyplataUsredniona}
Łączna wypłata \emph{uśredniona} wierzchołka $v$ jest równa
\[
U_{avg}(\mapaSy, \mapaSt, v) = \begin{cases}
	\frac{
		\sum_{w \in \neigh{v}} \fwwk^\mapaSy(v,w) \cdot u(\mapaSt(v), \mapaSt(w))
	}{\udeg{v}} &\text{ dla } \udeg{v} \neq 0 \\
	0 &\text { wpp.}
	\end{cases}
\]
\end{df}

\noindent
Dla przypadku $\udeg{v} = 0$ przyjęliśmy dla pełności, że wypłata gracza $v$
jest równa $0$. Nie będzie to jednak miało wpływu na dynamikę, gdyż gracz $v$
nie ma żadnych sąsiadów, na których ewolucję mógłby oddziaływać.

\subsection{Odwzorowanie $rand$}\label{rand}

Niech $\left(rand_{\tuple{v,w,t}}\right)_{\{v,w \in V \ t \in \nat\}}$ będzie
nieskończonym zbiorem niezależnych zmiennych losowych
$rand_{\tuple{v,w,t}} : \Omega \to [0,1]$ o rozkładzie jednostajnym na
przedziale $[0,1]$.
Dla wygody określamy funkcję 
$ \rand : V \times V \times \nat \times \Omega \to [0,1] $ następująco.
\begin{df}
\[ rand(v, w, t, \omega) = rand_{\tuple{v,w,t}}(\omega) \]
\end{df}

\subsection{Preferencje gracza}\label{preferencje}

Dynamikę grafu w uogólnionych grach przestrzennych wyrażamy
za pomocą wag krawędzi i relacji sympatii ---
w każdej turze gracz określa kogo darzy sympatią, a kogo nie.
Swoje sympatie w danej turze może uzależniać od map
strategii $\mapaSt$ oraz sympatii $\mapaSy$ z tury poprzedniej,
a także elementu losowego $\omega$.
Te zależności będziemy nazywali \emph{preferencjami gracza}.

\begin{df}
\emph{Preferencją} gracza nazwiemy dowolną funkcję
\[ \pref : \mapySy \times \mapySt \times V \times \neigh{V} \to [0,1]^{V \times V \times \nat \times \Omega} \]
\end{df}

\begin{df}
Preferencją \emph{przyjazną} nazwiemy funkcję
\[ \pi_{all}(\mapaSy, \mapaSt, v, w) = 1 \]
\end{df}

\begin{df}
Preferencją \emph{losową} nazwiemy funkcję
\[ \pi_{rnd}(\mapaSy, \mapaSt, v, w) = rand \]
\end{df}

\begin{df}
Preferencją \emph{wypłaty} nazwiemy funkcję
\[ \pi_{wyp}(\mapaSy, \mapaSt, v, w) =
	\begin{cases}
		1 &\text{ dla } \wyplata(\mapaSy, \mapaSt, w) \geq \wyplata(\mapaSy, \mapaSt, v) \\
		0 &\text{ wpp.}
	\end{cases}
\]
\end{df}

\begin{df}
Preferencją \emph{anty-zdrady} nazwiemy funkcję
\[ \pi_{antiD}(\mapaSy, \mapaSt, v, w) =
	\begin{cases}
		1 &\text{ dla } \mapaSt(w, v) = C \\
		0 &\text{ wpp.}
	\end{cases}
\]
\end{df}

\begin{df}
Preferencją \emph{współpracy} nazwiemy funkcję
\[ \pi_{proC}(\mapaSy, \mapaSt, v, w) =
	\begin{cases}
		1 &\text{ dla } \mapaSt(w, v) = C \\
		rand &\text{ wpp.}
	\end{cases}
\]
\end{df}

\noindent
Zbiór rozważanych preferencji oznaczamy
$\prefy = \{\pi_{all}, \pi_{rnd}, \pi_{wyp}, \pi_{antiD}, \pi_{proC}\}$.

\subsection{Typ gracza}\label{typ}

Często rozważanym zachowaniem gracza w teorii gier jest
taktyka ``wet za wet'' (ang. \emph{tit for tat}).
Aby móc ją zamodelować, zamiast przypisywać graczowi konkretną strategię,
uzależniamy jego decyzję od strategii jego przeciwnika w poprzedniej turze.
Przypadek, w którym gracze nie grali jeszcze ze sobą oznaczamy jako $\nieznany$.

\begin{df}\label{typGracza}
\emph{Typem} gracza nazwiemy dowolną funkcję
\[ \typ : S \cup \{\nieznany\} \to S \]
\end{df}

\noindent
W symulacjach rozważaliśmy następujące trzy typy graczy:
\begin{df}
Typem gracza $ALLC$ nazwiemy funkcję
\[ ALLC(s) = C \]
\end{df}
\begin{df}
Typem gracza $ALLD$ nazwiemy funkcję
\[ ALLD(s) = D \]
\end{df}
\begin{df}
Typem gracza $TFT$ nazwiemy funkcję
\[ TFT(s) =
	\begin{cases}
		C &\text{ dla } s \neq D \\
		D &\text{ dla } s = D
	\end{cases}
\]
\end{df}

Zbiór typów graczy będziemy oznaczali $\typy = \{ALLC, ALLD, TFT\}$.

\subsection{Charakter gracza}\label{charakter}

\begin{df}
\emph{Charakterem} gracza nazwiemy dowolną parę
$\tuple{\pref,\typ} \in \prefy \times \typy$.
\end{df}

\subsection{Mapa charakterów}\label{mapaCharakterow}

\begin{df}
\emph{Mapą charakterów} będziemy oznaczać dowolną funkcję
\[ \mapaC : V \to \prefy \times \typy \]
Zbiór wszystkich takich funkcji będziemy oznaczali jako $\mapyC = (\prefy \times \typy)^V$.
\end{df}

\subsection{Uogólniona gra przestrzenna}\label{uogolnionaGraPrzestrzenna}

Teraz dysponujemy już wszystkimi pojęciami niezbędnymi do zdefiniowania 
\emph{uogólnionej gry przestrzennej}.

\begin{df}
\emph{Uogólnioną grą przestrzenną} nazwiemy piątkę uporządkowaną
$\graUP = \tuple{\gra, \graf, \chary, \fwwk, \wyplata}$, gdzie

\medskip

\begin{tabular}{ll}
$\gra$ & --- symetryczna gra dwuosobowa (patrz \ref{graSymDwuosobowa}), \\
$\graf$ & --- skończony graf nieskierowany (patrz \ref{graf}), \\
$\chary$ & --- zbiór charakterów graczy biorących udział w grze (patrz \ref{charakter}), \\
$\fwwk$ & --- funkcja wyboru wagi krawędzi (patrz \ref{fwwk}), \\
$\wyplata$ & --- model naliczania łącznej wypłaty (patrz \ref{laczneWyplaty}).
\end{tabular}
\end{df}

\medskip

\subsection{Uogólniony profil przestrzenny}\label{uogolnionyProfilPrzestrzenny}

Uogólniony profil przestrzenny jest jednym z najistotniejszych pojęć
naszej pracy. Jego elementy to:

\medskip

\begin{tabular}{ll}
$\mapaSy : V \times \neigh{V} \to [0,1]$ & --- mapy sympatii \\
$\mapaSt : V \to S$      & --- mapy strategii \\
$\mapaC : V \to \prefy \times \typy$   & --- mapy charakterów \\
\end{tabular}

\medskip

\begin{df}
Niech $\graUP = \tuple{\gra, \graf, \chary, \fwwk, \wyplata}$ będzie pewną
uogólnioną grą przestrzenną.
\emph{Uogólnionym profilem przestrzennym} gry $\graUP$ nazwiemy każdą trójkę
uporządkowaną
\[ \upp = \tuple{\mapaSy, \mapaSt, \mapaC}, \]
gdzie $\mapaSy \in \mapySy$, $\mapaSt \in \mapySt$, $\mapaC \in \mapyC$.
Zbiór wszystkich uogólnionych profili przestrzennych oznaczamy podobnie
do profili przestrzennych przedstawionych w punkcie \ref{profilPrzestrzenny},
przez  $\uppy = \mapySy \times \mapySt \times \mapyC$.
\end{df}

\section{Dynamika} % selekcja + nowy graf
\label{dynamikaUogolnionejGryPrzestrzennej}

\begin{df}
Niech $\graUP$ będzie uogólnioną grą przestrzenną, a $\upp_0$
jej pewnym uogólnionym profilem przestrzennym.
\emph{Dynamiką} gry $\graUP$ nazwiemy
ciąg zmiennych losowych $(X_t)_{t\in\nat}$ taki, że
$ X_t : \Omega \to \uppy $ oraz $ X_0(\omega) = \upp_0$.
Profil $\upp_0$ będziemy nazywali stanem początkowym tej dynamiki.
\end{df}

\noindent
Rozpatrywane przez nas dynamiki to ciągi, których kolejne wyrazy
\[ X_{t+1}(\omega) = \tuple{\mapaSy_{t+1}, \mapaSt_{t+1}, \mapaC_{t+1}} \]
wyznaczane są na podstawie poprzednich
\[ X_t(\omega) = \tuple{\mapaSy_t, \mapaSt_t, \mapaC_t} \]
gdzie
\begin{align}
\label{eq:MapaSy}
\mapaSy_{t+1}(v,w) &= f_\mapaSy(\mapaSy_t, \mapaSt_t, v, w)(v, w, t+1, \omega)\\
\label{eq:MapaSt}
\mapaSt_{t+1}(v,w) &= f_\mapaSt(\mapaSt_t'(w,v))
\end{align}
\begin{align*}
\tuple{f_\mapaSy,f_\mapaSt} &= \mapaC_{t+1}(v) \\
\mapaSt_t'(v,w) &=
	\begin{cases}
		\mapaSt_t(v,w) & \text{ dla } \mapaC_{t+1}(v) = \mapaC_t(v) \\
		\nieznany & \text{ wpp. }
	\end{cases}
\end{align*}
Najważniejszy wzór opisujący $\mapaC_{t+1}$ określamy w poszczególnych
definicjach.

\bigskip

Jeżeli nie określono inaczej, losowym wierzchołkiem nazywamy
dowolny element zbioru $V$, przy czym prawdopodobieństwo
wyboru każdego z nich jest takie samo.
Analogicznie losowym sąsiadem wierzchołka $v$ będzie element losowo wybrany
ze zbioru $\neigh{v}$ sąsiadów $v$, przy czym prawdopodobieństwo
wyboru wszystkich elementów tego zbioru jest równe.

\medskip

\noindent
Wśród rozważanych dynamik znalazły się:

%\begin{df} Dynamika imitacji asynchroniczna
%
%\noindent
%Niech $v_0$ będzie losowym wierzchołkiem, a $w_0$ jego losowym sąsiadem, wtedy
%\begin{align*}
%\mapaC_{t+1}(v) &=
%	\begin{cases}
%		\mapaC_t(w_0) &\text{ dla } v = v_0 \land
%			\wyplata(\mapaSy_t, \mapaSt_t, v_0) < \wyplata(\mapaSy, \mapaSt_t, w_0) \\
%		\mapaC_t(v) &\text{ dla } v \neq v_0
%	\end{cases}
%\end{align*}
%\end{df}
%
%\begin{df} Dynamika imitacji synchroniczna
%
%\noindent
%Dla każdego wierzchołka $v$ niech $w_v$ będzie jego losowym sąsiadem, wtedy
%\begin{align*}
%\mapaC_{t+1}(v) &=
%	\begin{cases}
%		\mapaC_t(w_v) &\text{ dla } 
%			\wyplata(\mapaSy_t, \mapaSt_t, v) < \wyplata(\mapaSy, \mapaSt_t, w_v) \\
%		\mapaC_t(v) &\text{ wpp. }
%	\end{cases}\end{align*}
%\end{df}
%

\begin{df} Dynamika kanonicznego procesu Morana, asynchroniczna
\label{pierwszaDynamika}

\noindent
Niech $v_0$ będzie losowym wierzchołkiem, a $w_0$ jego losowym
sąsiadem, wtedy
\begin{align*}
p_t &= \begin{cases}
	\frac{
		max\left\{
			\wyplata(\mapaSy_t, \mapaSt_t, w_0) -
			\wyplata(\mapaSy_t, \mapaSt_t, v_0),
		0\right\}
	}{ (T - S) max \left\{ \udeg{v_0}, \udeg{w_0} \right\} }
	& \text { dla } \udeg{v_0} \neq 0 \lor \udeg{w_0} \neq 0 \\
	0 & \text{ wpp.}
	\end{cases} \\
\mapaC_{t+1}(v) &=
	\begin{cases}
		\mapaC_t(w_0) &\text{ dla } v = v_0
			\text{ z prawdopodobieństwem } p_t \\
		\mapaC_t(v_0) &\text{ dla } v = v_0
			\text{ z prawdopodobieństwem } 1-p_t \\
		\mapaC_t(v) &\text{ wpp. }
	\end{cases}
\end{align*}
\end{df}

\begin{df} Dynamika kanonicznego procesu Morana, synchroniczna

\noindent
Dla każdego wierzchołka $v$ niech $w_v$ będzie jego losowym sąsiadem, wtedy
\begin{align*}
p_{t,v} &= \begin{cases}
	\frac{
		max\left\{
			\wyplata(\mapaSy_t, \mapaSt_t, w_v) -
			\wyplata(\mapaSy_t, \mapaSt_t, v),
		0\right\}
	}{ (T-S) max \left\{ \udeg{v}, \udeg{w_v} \right\} }
	& \text { dla } \udeg{v} \neq 0 \lor \udeg{w_v} \neq 0 \\
	0 & \text { wpp.}
	\end{cases} \\
\mapaC_{t+1}(v) &=
	\begin{cases}
		\mapaC_t(w_v) &\text{ z prawdopodobieństwem } p_{t,v} \\
		\mapaC_t(v) &\text{ z prawdopodobieństwem } 1-p_{t,v}
	\end{cases}
\end{align*}
\end{df}

\begin{df} Dynamika sprawiedliwego procesu Morana, asynchroniczna

\noindent
Niech $v_0$ będzie losowym wierzchołkiem, a $w_0$ jego losowym
sąsiadem, wtedy
\begin{align*}
p_t &= \begin{cases}
	max\left\{
		\frac{\wyplata(\mapaSy_t, \mapaSt_t, w_0)}{ (T-S) \udeg{w_0} } -
		\frac{\wyplata(\mapaSy_t, \mapaSt_t, v_0)}{ (T-S) \udeg{v_0} }
		, 0 \right\} & \text { dla } \udeg{v_0} \neq 0 \land \udeg{w_0} \neq 0 \\
		0 & \text{ wpp.}
	\end{cases} \\
\mapaC_{t+1}(v) &=
	\begin{cases}
		\mapaC_t(w_0) &\text{ dla } v = v_0
			\text{ z prawdopodobieństwem } p_t \\
		\mapaC_t(v_0) &\text{ dla } v = v_0
			\text{ z prawdopodobieństwem } 1-p_t \\
		\mapaC_t(v) &\text{ wpp. }
	\end{cases}
\end{align*}
\end{df}

\begin{df} Dynamika sprawiedliwego procesu Morana, synchroniczna

\noindent
Dla każdego wierzchołka $v$ niech $w_v$ będzie jego losowym sąsiadem, wtedy
\begin{align*}
p_{t,v} &= \begin{cases}
	max\left\{
		\frac{\wyplata(\mapaSy_t, \mapaSt_t, w_v)}{ (T-S) \udeg{w_v} } -
		\frac{\wyplata(\mapaSy_t, \mapaSt_t, v)}{ (T-S) \udeg{v} }
		, 0 \right\} & \text { dla } \udeg{v} \neq 0 \land \udeg{w_v} \neq 0 \\
		0 & \text{ wpp.}
	\end{cases} \\
\mapaC_{t+1}(v) &=
	\begin{cases}
		\mapaC_t(w_v) &\text{ z prawdopodobieństwem } p_{t,v} \\
		\mapaC_t(v) &\text{ z prawdopodobieństwem } 1-p_{t,v}
	\end{cases}
\end{align*}
\end{df}

\begin{df} Dynamika głosowania, asynchroniczna

\noindent
Niech $v_0$ będzie losowym wierzchołkiem, a
para $winner_t = \tuple{\typ_{t}, \pref_{t}}$ będzie parą
o największej wartości funkcji $count_{t} : \typy \times \prefy \to \real$
określonej jako 
\[ count_{t}(\typ, \pref) = \sum_{w \in W} \wyplata(\mapaSy_t, \mapaSt_t, w) \]
gdzie $ W = \{ w \in \neigh{v_0} \cup \{v_0\} \ |
\ \mapaC_t(w) = \typ \land \mapaC_t(w) = \pref \} $, % tu nie ma być indeksów, bo to parametry $count$
wtedy
\begin{align*}
\mapaC_{t+1}(v) &=
	\begin{cases}
		winner_{t} & \text{ dla } v = v_0 \\
		\mapaC_{t}(v) & \text{ wpp.}
	\end{cases}
\end{align*}
\end{df}

\begin{df} Dynamika głosowania, synchroniczna

\label{ostatniaDynamika}
\noindent
Niech para $winner_{t,v} = \tuple{\pref_{t,v}, \typ_{t,v}}$ będzie charakterem
o największej wartości funkcji $count_{t,v} : \prefy \times \typy \to \real$
określonej jako
\[ count_{t,v}(\pref, \typ) = \sum_{w \in W} \wyplata(\mapaSy_t, \mapaSt_t, w) \]
gdzie $ W = \{ w \in \neigh{v} \cup \{v\} \ |
\ \mapaC_t(w) = \tuple{\pref, \typ} \} $, % tu nie ma być indeksów, bo to parametry $count$
wtedy
\begin{align*}
\mapaC_{t+1}(v) &= winner_{t,v}
\end{align*}
\end{df}

\subsection{Dynamika z mutacją}

W celu uwiarygodnienia modelu, wprowadzamy parametr $\epsilon$ określający
prawdopodobieństwo losowej mutacji.
Niech $\mapaC_{t+1}$ będzie mapą charakterów w chwili $(t+1)$ dla
pewnej dynamiki. Wtedy dla wersji asynchronicznej
\[ \mapaC_{t+1}^\epsilon(v) = 
	\begin{cases}
		\mapaC_{t+1}(v) & \text{ dla } v \neq v_0 \\
		\mapaC_{t+1}(v_0) & \text{ dla } v = v_0 \text{ z prawdopodobieństwem } 1 - \epsilon \\
		\tuple{\pref_0, \typ_0} & \text{ dla } v = v_0 \text { z prawdopodobieństwem } \epsilon
	\end{cases}
\]
oraz dla wersji synchronicznej
\[ \mapaC_{t+1}^\epsilon(v) = 
	\begin{cases}
		\mapaC_{t+1}(v) & \text{ z prawdopodobieństwem } 1 - \epsilon \\
		\tuple{\pref_v, \typ_v} & \text { z prawdopodobieństwem } \epsilon
	\end{cases}
\]
gdzie $\tuple{\pref_0, \typ_0}$ i $\tuple{\pref_v, \typ_v}$ są losowymi elementami
zbioru $\chary$ (różnymi dla każdego $v$ i $t$).

\section{Dynamiki uogólnionych gier przestrzennych jako łańcuchy Markowa}
\label{dynamikaJakoLancuchMarkowa}

Dynamikę uogólnionej gry przestrzennej określiliśmy jako ciąg zmiennych
losowych $(X_t)_{t \in \nat}$.
W tej części zastanowimy się jakie własności
mają dynamiki zdefiniowane w punktach \ref{pierwszaDynamika}--\ref{ostatniaDynamika}.

Chcąc przedstawić je jako łańcuchy Markowa potrzebujemy, aby
zbiory osiąganych przez nie stanów były skończone.
% LBK: A może:
% ``Chielibyśmy móc je przedstawić w postaci łańcuchów Markowa. Pierwszym
% krokiem w tym kierunku jest uczynienie zbioru osągalnych przez nie stanów
% skończonym''.
% DL: a moze poszli do lasu? nie :-P
% DL: NIE :D
W tym celu dyskretyzujemy liczby rzeczywiste.
Sympatia jest liczbą z przedziału $[0,1]$, więc jest ograniczona.
Ponadto zbiory $S$, $\prefy$ oraz $\typy$ są skończone z definicji, zatem
możemy przyjąć, że zbiór wszystkich uogólnionych profili przestrzennych jest skończony.
Dodatkowo ze względów technicznych wykluczamy z niego elementy nieprawidłowe, tzn. takie,
w których $\mapaSy(v,w)$ i $\mapaSt$ nie spełniają wzorów \eqref{eq:MapaSy} oraz \eqref{eq:MapaSt}.

\subsection{Własność Markowa}

Wszystkie przedstawione definicje dynamik mają postać ciągu rekurencyjnego
\[ X_{t+1} = f(X_t,t). \]
Zmienna $t$ jest używana tylko do odróżnienia chwili poprzedniej $t$ od następnej $(t+1)$.
% LBK: Ja bym powyższe napisał:
% \[ X_{t+1} = f(X_t). \]
% Wobec tego kolejny wyraz zależy tylko od poprzedniego.
Ponadto ciąg $(X_t)_{t \in \nat}$ zależy od zbioru zmiennych losowych
$rand_{v,w,t}$, wyboru losowego wierzchołka $v$ wraz z sąsiadem $w_v$ (dla każdej chwili $t$),
a także od mutacji (w przypadku modeli je uwzględniających).
Biorąc pod uwagę niezależność wszystkich wspomnianych zmiennych losowych
wnioskujemy, że ciągi \ref{pierwszaDynamika}--\ref{ostatniaDynamika} są łańcuchami Markowa.

\subsection{Inne własności}

Dla dynamik bez mutacji w łańcuchu istnieje co najmniej tyle stanów pochłaniających
jaka jest liczność zbioru charakterów, dlatego nie są one nieprzywiedlne.

W przypadku dynamik z mutacjami istnieje dodatnie prawdopodobieństwo wystąpienia mutacji
 dla każdego gracza po kolei (w przypadku dynamiki asynchronicznej)
lub wszystkich naraz (dla dynamiki synchronicznej). Z tego powodu istnieje niezerowe
prawdopodobieństwo dojścia do każdego stanu prawidłowego, zatem łańcuchy 
odpowiadające tym dynamikom są nieprzywiedlne.
Ponadto do każdego stanu można przejść do niego samego w jednym kroku (np.
mutując graczy tak, aby nie zmienili strategii).
To gwarantuje, że nasze łańcuchy są nieokresowe, a więc też ergodyczne.
Wobec tego z twierdzenia \emph{Ergodycznego} \ref{twErgodyczne} wynika, że
dynamiki z mutacjami posiadają tylko jeden rozkład stacjonarny.

Ten rozkład odpowiada na pytanie do czego zmierza populacja w wyniku ewolucji.
Niestety z uwagi na ogromną liczbę możliwych stanów, rosnącą wykładniczo
względem rozmiaru grafu $N$, dokładne wyznaczenie rozkładu stacjonarnego jest
obecnie daleko poza możliwościami obliczeniowymi komputerów.
\footnote{Już dla kwadratowej siatki o boku 100 i dwóch różnych typów 
graczy mamy $2^{10000}>10^{3000}$ możliwych stanów. Dla porównania dodajmy,
że liczbę wszystkich cząstek we wszechświecie szacuje się na $10^{80}$.}
Z tego powodu w naszych badaniach wyznaczamy tylko przybliżenia szukanych
rozkładów, posługując się przy tym metodą \emph{Monte Carlo}.
